\documentclass{ctexart}

\usepackage{amsmath}
\usepackage{amssymb}

\title{1.8.1 Theoretical questions}


\author{邵柯欣 \\ 专业：信息与计算科学  学号：3200103310}

\begin{document}

\maketitle

\section{$\uppercase\expandafter{\romannumeral1}$}
\subsection{What is the width of the interval at the nth step?}
解：\\
二分法每循环一次区间的长度会缩短$\frac{1}{2}$。\\
区间的原始长度$l_0 = 3.5-1.5 = 2$。\\
所以，第n次循环时区间的长度$l_n = \frac{2}{2^n}$。\\
\subsection{What is the supremum of the distance between the root r and the midpoint of the interval?}
解：\\
根r和区间中点之间的上确界为区间长度的一半，即$\frac{l_n}{2} = \frac{1}{2^n}$。

\section{$\uppercase\expandafter{\romannumeral2}$}
证：\\
令$x_n$为我们我们经过n次循环确定的根，$x^*$为真实的根。\\
由上题可知，$|x_n-x^*| < \frac{b_0-a_0}{2^{n+1}}$。我们需要使得$|x_n-x^*| < \varepsilon$。\\
所以需要$\frac{b_0-a_0}{2^{n+1}} \le \varepsilon$。\\
变换之后，得$log(\varepsilon)+(n+1)*log(2) \ge log(b_0-a_0)$。\\
所以，$n \ge \frac{log(b_0-a_0)-log(\varepsilon)}{log2}-1$。\\

\section{$\uppercase\expandafter{\romannumeral3}$}
解：\\
$p(x) = 4*x^3-2*x^2+3 = 0, x_0 = -1, n=4$\\
所以$p'(x) = 12*x^2-4*x$.\\
Newton's method: $x_{n+1} = x_n-\frac{p(x_n)}{p'(x_n)}$.\\
$x_0 = -1.00000, p(x_0) = -3.00000, p'(x_0) = 16.00000$\\
$x_1 = -0.81250, p(x_1) = -0.46582, p'(x_1) = 11.17188$\\
$x_2 = -0.77080, p(x_2) = -0.02010, p'(x_2) = 10.21279$\\
$x_3 = -0.76883, p(x_3) = -0.00002, p'(x_3) = 10.16851$\\
$x_4 = -0.76883, p(x_4) = -0.00002, p'(x_4) = 10.16851$\\

\section{$\uppercase\expandafter{\romannumeral4}$}
解：\\
牛顿法的变体：$x_{n+1} = x_n-\frac{f(x_n)}{f'(x_0)}$。\\
要求C和s，使得$e_{n+1} = C*e_n^s$，$e_n$为第n步的误差。

\section{$\uppercase\expandafter{\romannumeral5}$}
证：\\
$(-\frac{\pi}{2},\frac{\pi}{2}),x_{n+1} = tan^{-1}x_n$，令$y = tan^{-1}x$，\\
$y' = -\frac{1}{sin^2(x)},x \in (-\frac{\pi}{2},\frac{\pi}{2})$，所以$y' < -1$。\\
所以$|x_{n+1}-x_{n}| = |tan^{-1}x_n-tan^{-1}x_{n-1}| > |x_n - x_{n-1}|$。\\
因此不收敛。

\section{$\uppercase\expandafter{\romannumeral6}$}
解：\\
令$x_{n+1} = \frac{1}{p+x_n},x_1 = \frac{1}{p}$，所求$x$为$x_n$的极限。\\
因为$x_n > 0,p > 1$。\\
所以$x_{n+1} < x_n$。\\
$x_{n}-x_{n+1} = \frac{1}{p+x_{n-1}}-\frac{1}{p+x_n} = \frac{x_{n-1}-x_{n}}{(p+x_n)*(p+x_{n-1})} < \frac{x_{n-1}-x_{n}}{(1+x_{n})^2}$\\
所以$\frac{x_{n}-x_{n+1}}{x_{1}-x_{2}} < \frac{1}{(1+x_{n})^{2*(n-1)}}$，\\
取极限可得$\lim_{n \to \infty}x_{n}-x_{n+1} = 0$。\\
所以${x_n}$收敛成立，x为不动点。\\
所以$x=\frac{1}{p+x}$，即，$x = -\frac{p}{2}+\sqrt(1+\frac{p^2}{4})$。

\section{$\uppercase\expandafter{\romannumeral7}$}
解：\\
$n \ge \frac{log(b_0-a_0)-log(e)}{log2}-1$。

\end{document}
